The problem can be found at the following link: Question Link
This is a question of the take-non take type of dynamic programming, which involves breaking a string into multiple strings based on a specific condition. So I also used dynamic programming to solve this problem.
- I define a recursive function
solve
to compute the number of distinct occurrences of stringt
in strings
starting from indicesi
andj
. - At each step, we have two choices:
- Not take the current character of
s
. - If the current character of
s
matches the current character oft
, then we advance both pointers.
- Not take the current character of
- We memoize the results to avoid redundant computations.
- Time Complexity:
(O(n x m))
, where(n)
is the length of strings
and(m)
is the length of stringt
. - Auxiliary Space Complexity:
(O(n x m))
due to the memoization table.
class Solution {
public:
int mod = 1e9 + 7;
int solve(int i, int j, int n, int m, string s, string t, vector<vector<int>>& dp) {
if (j == m)
return 1;
if (i == n)
return 0;
if (dp[i][j] != -1)
return dp[i][j];
int ntake = solve(i + 1, j, n, m, s, t, dp);
int take = 0;
if (s[i] == t[j])
take = solve(i + 1, j + 1, n, m, s, t, dp);
return dp[i][j] = (take + ntake) % mod;
}
int subsequenceCount(string s, string t) {
int n = s.size(), m = t.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
return solve(0, 0, n, m, s, t, dp);
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.